class Solution
{
public:
    // BFS, 超时
    vector<int> maxPoints(vector<vector<int>> &grid, vector<int> &queries)
    {
        int m = grid.size();
        int n = grid[0].size();
        map<int, int> queryCanReach;
        for (auto &row : grid)
        {
            for (int num : row)
            {
                queryCanReach[num] = 0;
            }
        }

        // 维护不可达区域的边界
        set<vector<int>> unreachableBoundary;
        unreachableBoundary.insert({0, 0});

        // 矩阵中的元素是query的分界线
        auto query = queryCanReach.begin();
        ++query;

        while (!unreachableBoundary.empty() && query != queryCanReach.end())
        {
            int increasedReachCount = 0;

            // 更新不可达边界
            set<vector<int>> newUnreachable;
            for (auto &position : unreachableBoundary)
            {
                int x = position[0];
                int y = position[1];
                if (grid[x][y] < query->first)
                {
                    grid[x][y] = INT_MAX;
                    ++increasedReachCount;
                    if (x > 0 && grid[x - 1][y] != INT_MAX)
                    {
                        if (!unreachableBoundary.count({x - 1, y}))
                        {
                            newUnreachable.insert({x - 1, y});
                        }
                    }
                    if (y > 0 && grid[x][y - 1] != INT_MAX)
                    {
                        if (!unreachableBoundary.count({x, y - 1}))
                        {
                            newUnreachable.insert({x, y - 1});
                        }
                    }
                    if (x < m - 1 && grid[x + 1][y] != INT_MAX)
                    {
                        if (!unreachableBoundary.count({x + 1, y}))
                        {
                            newUnreachable.insert({x + 1, y});
                        }
                    }
                    if (y < n - 1 && grid[x][y + 1] != INT_MAX)
                    {
                        if (!unreachableBoundary.count({x, y + 1}))
                        {
                            newUnreachable.insert({x, y + 1});
                        }
                    }
                }
                else
                {
                    newUnreachable.insert({x, y});
                }
            }
            newUnreachable.swap(unreachableBoundary);

            if (increasedReachCount == 0)
            {
                auto curQuery = query;
                ++query;
                if (query == queryCanReach.end())
                {
                    break;
                }
                queryCanReach[query->first] = queryCanReach[curQuery->first];
            }
            else
            {
                queryCanReach[query->first] += increasedReachCount;
            }
        }
        queryCanReach[INT_MAX] = m * n;

        int answerSize = queries.size();
        vector<int> answer;
        answer.reserve(answerSize);

        auto compare = [](int q, auto &pair)
        { return q <= pair.first; };

        for (int query : queries)
        {
            auto pos = upper_bound(queryCanReach.begin(), queryCanReach.end(), query, compare);
            answer.push_back(pos->second);
        }
        return answer;
    }
};